/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：RadixSort.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-29
Function List ：
Description   ：Radix Sort
******************************************************/

#include "RadixSort.h"
#include <stdlib.h>  // for malloc
#include "FatalError.h"

#define MaxDigit    4
#define MaxRadixNum 10

typedef struct Node *PtrToNode;

struct Node {
    ElementType Key;
    PtrToNode   Next;
};

typedef struct HeadNode {
    PtrToNode Head;
    PtrToNode Tail;
} *Bucket;

// Static Function Lists
static int GetDigit(ElementType X, int D);
static Bucket InitializeBucket();

static int GetDigit(ElementType X, int D) {
    int d;
    int i;

    d = 0;
    for (i = 1; i <= D; ++i) {
        d = X % MaxRadixNum;
        X /= MaxRadixNum;
    }

    return d;
}

static Bucket InitializeBucket() {
    Bucket B;
    int i;

    B = (Bucket)malloc(MaxRadixNum * sizeof(struct HeadNode));
    if (B == NULL) {
        FatalError("Out of space!!!");
    } else {
        for (i = 0; i < MaxRadixNum; ++i) {
            B[i].Head = NULL;
            B[i].Tail = NULL;
        }
    }

    return B;
}

void RadixSort(ElementType A[], int N) {
    int i;
    int D;
    int Di;
    Bucket B;
    PtrToNode P;
    PtrToNode Tmp;
    PtrToNode List;

    /* Initialize the bucket */
    B = InitializeBucket();

    /* Put the elements in the bucket */
    List = NULL;
    for (i = 0; i < N; ++i) {
        Tmp = (PtrToNode)malloc(sizeof(struct Node));
        if (Tmp == NULL) {
            FatalError("Out of space!!!");
        }

        Tmp->Key = A[i];
        Tmp->Next = List;
        List = Tmp;
    }

    // Radix Sort
    for (D = 1; D <= MaxDigit; ++D) {
        P = List;
        while (P != NULL) {
            Di = GetDigit(P->Key, D);
            Tmp = P;
            P = P->Next;
            Tmp->Next = NULL;
            if (B[Di].Head == NULL) {
                B[Di].Head = Tmp;
                B[Di].Tail = Tmp;
            } else {
                B[Di].Tail->Next = Tmp;
                B[Di].Tail = Tmp;
            }
        }

        List = NULL;
        for (Di = MaxRadixNum - 1; Di >= 0; --Di) {
            if (B[Di].Head != NULL) {
                B[Di].Tail->Next = List;
                List = B[Di].Head;
                B[Di].Head = NULL;
                B[Di].Tail = NULL;
            }
        }
    }

    /* Free allocated space */
    for (i = 0; i < N; ++i) {
        Tmp = List;
        List = List->Next;
        A[i] = Tmp->Key;
        free(Tmp);
    }
}

// EOF

